//给你一个整数数组 digits ，其中每个元素是一个数字（0 - 9）。数组中可能存在重复元素。 
//
// 你需要找出 所有 满足下述条件且 互不相同 的整数： 
//
// 
// 该整数由 digits 中的三个元素按 任意 顺序 依次连接 组成。 
// 该整数不含 前导零 
// 该整数是一个 偶数 
// 
//
// 例如，给定的 digits 是 [1, 2, 3] ，整数 132 和 312 满足上面列出的全部条件。 
//
// 将找出的所有互不相同的整数按 递增顺序 排列，并以数组形式返回。 
//
// 
//
// 示例 1： 
//
// 
//输入：digits = [2,1,3,0]
//输出：[102,120,130,132,210,230,302,310,312,320]
//解释：
//所有满足题目条件的整数都在输出数组中列出。 
//注意，答案数组中不含有 奇数 或带 前导零 的整数。 
//
// 示例 2： 
//
// 
//输入：digits = [2,2,8,8,2]
//输出：[222,228,282,288,822,828,882]
//解释：
//同样的数字（0 - 9）在构造整数时可以重复多次，重复次数最多与其在 digits 中出现的次数一样。 
//在这个例子中，数字 8 在构造 288、828 和 882 时都重复了两次。 
// 
//
// 示例 3： 
//
// 
//输入：digits = [3,7,5]
//输出：[]
//解释：
//使用给定的 digits 无法构造偶数。
// 
//
// 
//
// 提示： 
//
// 
// 3 <= digits.length <= 100 
// 0 <= digits[i] <= 9 
// 
//
// Related Topics 数组 哈希表 枚举 排序 👍 47 👎 0


package LeetCode.editor.cn;


import java.util.*;

/**
 * @author ldltd
 * @date 2025-05-12 09:07:08
 * @description 2094.找出 3 位偶数
 
 */
 
public class Finding3DigitEvenNumbers {
    public static void main(String[] args) {
    //测试代码
    Finding3DigitEvenNumbers fun = new Finding3DigitEvenNumbers();
    Solution solution= fun.new Solution();
    solution.findEvenNumbers(new  int[]{2,1,3,0});
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    boolean[] vis;
    Set<Integer> resultSet = new HashSet<>();  // 使用Set去重

    public int[] findEvenNumbers1(int[] digits) {
        int len = digits.length;
        vis = new boolean[len];
        dfs(digits, 0, 0);

        // 转换为数组并排序
        int[] ans = new int[resultSet.size()];
        int idx = 0;
        for (int num : resultSet) {
            ans[idx++] = num;
        }
        Arrays.sort(ans);
        return ans;
    }

    private void dfs(int[] digits, int idx, int current) {
        if (idx == 3) {
            if (current % 2 == 0) {  // 确保是偶数
                resultSet.add(current);
            }
            return;
        }

        for (int i = 0; i < digits.length; i++) {
            if (!vis[i]) {
                if (idx == 0 && digits[i] == 0) {  // 第一位不能为0
                    continue;
                }
                vis[i] = true;
                dfs(digits, idx + 1, current * 10 + digits[i]);
                vis[i] = false;  // 回溯
            }
        }
    }
    //直接枚举所有的三位偶数
    public int[] findEvenNumbers(int[] digits) {
        List<Integer> res = new ArrayList<>();
        Map<Integer, Integer> freq = new HashMap<>();
        // 统计数字数组中各数字的出现次数
        for (int d : digits) {
            freq.put(d, freq.getOrDefault(d, 0) + 1);
        }
        // 枚举所有三位偶数
        for (int i = 100; i < 1000; i += 2) {
            Map<Integer, Integer> freq1 = new HashMap<>();
            int num = i;
            // 统计当前偶数的每一位数字的出现次数
            while (num > 0) {
                int d = num % 10;
                freq1.put(d, freq1.getOrDefault(d, 0) + 1);
                num /= 10;
            }
            // 检查是否满足条件
            boolean isValid = true;
            for (Map.Entry<Integer, Integer> entry : freq1.entrySet()) {
                if (freq.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                res.add(i);
            }
        }
        // 转换为数组
        int[] result = new int[res.size()];
        for (int j = 0; j < res.size(); j++) {
            result[j] = res.get(j);
        }
        return result;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
